﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class Transit
    {
        public Transit()
        {
            int testCase = Int32.Parse(TestConsole.ReadLine());
            while (testCase-- > 0)
            {
                string[] inputString = TestConsole.ReadLine().Trim().Split(' ');
                int cityCount = Int32.Parse(inputString[0]);
                int roadCount = Int32.Parse(inputString[1]);
                int[,] distance = new int[cityCount, cityCount];
                int[,] connected = new int[cityCount, cityCount];
                bool[] closeCity = new bool[cityCount];
                int[] totalDistance = new int[cityCount];
                for (int i = 0; i < roadCount; i++)
                {
                    inputString = TestConsole.ReadLine().Trim().Split(' ');
                    int from = Int32.Parse(inputString[0].Trim());
                    int to = Int32.Parse(inputString[1].Trim());
                    int dist = Int32.Parse(inputString[2].Trim());
                    distance[from, to] = dist;
                    distance[to, from] = dist;
                    connected[from, ++connected[from, 0]] = to;
                    connected[to, ++connected[to, 0]] = from;
                    
                }
                Queue<int> queue = new Queue<int>();
                queue.Enqueue(0);
                while (queue.Count > 0)
                {
                    int from = queue.Dequeue();
                    closeCity[from] = true;
                    for (int i = 1; i <= connected[from, 0]; i++)
                    {
                        int to = connected[from, i];
                        if (closeCity[to])
                        {
                            continue;
                        }
                        if (totalDistance[to] == 0 || totalDistance[from] + distance[from, to] < totalDistance[to])
                        {
                            totalDistance[to] = totalDistance[from] + distance[from, to];
                            queue.Enqueue(to);
                        }
                    }
                }
                Console.WriteLine(totalDistance[cityCount - 1]);
            }
        }
    }
}
